class Graph {
public:
	Graph(){}
	Graph(const vector< vector<bool> > &mp): map(mp) {}
	void createGraph();
	bool isBipartiteGraph(vector<int> &parta, vector<int> &partb);
	int maxMatching(const vector<int> &parta, const vector<int> &partb);
	friend ostream& operator << (ostream &out, const Graph &G);
private:
    vector< vector<bool> > map;
	bool dfs_partite(int cur, vector<int> &parta, vector<int> &partb, vector<bool> &visited, vector<int> &partite);
	bool dfs_match(int boy, vector<int> &boys, vector<int> &girls, vector<bool> &visited);
};

//maxMatching
int Graph::maxMatching(const vector<int> &parta, const vector<int> &partb) {
	vector<int> boys(map.size(), -1), girls(map.size(), -1);
	int maxmatch = 0;
    for (int boy : parta) {
        vector<bool> visited(map.size(), false);
        if (dfs_match(boy, boys, girls, visited))
            maxmatch += 1;
	}
	return maxmatch;
}
bool Graph::dfs_match(int boy, vector<int> &boys, vector<int> &girls, vector<bool> &visited) {
	for (int i = 0; i != map.size(); ++i) {
		if (map[boy][i] && !visited[i]) {
			visited[i] = true;
			if (girls[i] == -1 || dfs_match(girls[i], boys, girls, visited)) {
				boys[boy] = i;
				girls[i] = boy;
				return true;
			}
		}
	}
	return false;
}

//isBipartiteGraph
bool Graph::isBipartiteGraph(vector<int> &parta, vector<int> &partb) {
	vector<bool> visited(map.size(), false);
	vector<int> partite(map.size(), -1);
	parta.clear(); partb.clear();
	for (int i = 0; i != map.size(); ++i) {
		if (!visited[i]) {
			bool flag = dfs_partite(i, parta, partb, visited, partite);
			if (!flag) {
				parta.clear(); partb.clear(); return false;
			}
		}
	}
	return true;
}
bool Graph::dfs_partite(int cur, vector<int> &parta, vector<int> &partb, vector<bool> &visited, vector<int> &partite) {
	visited[cur] = true;
	bool black = false, white = false;
	for (int i = 0; i != map.size(); ++i) {
		if (map[cur][i]) {
			if (partite[i] == 0)
				black = true;
			else if (partite[i] == 1)
				white = true;
		}
	}
	if (black && white)
		return false;
	if (black) {
		partite[cur] = 1;
		parta.push_back(cur);
	}
	else {
		partite[cur] = 0;
		partb.push_back(cur);
	}
	for (int i = 0; i != map.size(); ++i) {
		if (map[cur][i] && !visited[i]) {
			bool flag = dfs_partite(i, parta, partb, visited, partite);
			if (!flag)
				return false;
		}
	}
	return true;
}
//init&print Graph
void Graph::createGraph() {
	int size, arcnum, v1, v2;
	cout << "input the number of vertexs & arcs: ";
	cin >> size >> arcnum;
	cout << "input the arc: " << endl;
	map = vector< vector<bool> >(size, vector<bool>(size, false));
	for (int i = 0; i != arcnum; ++i) {
		cin >> v1 >> v2;
		map[v1][v2] = map[v2][v1] = true;
	}
}

ostream& operator << (ostream &out, const Graph &G) {
	for (int i = 0; i != (G.map).size(); ++i) {
		for (int j = 0; j != (G.map).size(); ++j)
			out << (G.map)[i][j] << " ";
		out << endl;
	}
	return out;
}